/********************************************
 *      排序
 * Created by zlj on 2024/6/29.
********************************************/
#include "Sort.h"

/**
 * 选择排序
 * @param arr
 * @param len
 */
void SelectSort(ElemType arr[], int len, int sort_type)
{
    int temp;
    for (int i = 0; i < len - 1; ++i)
    {
        for (int j = i + 1; j < len; ++j)
        {
            if (sort_type)
            {
                if (arr[i] > arr[j])
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            } else
            {
                if (arr[i] < arr[j])
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}

/**
 * 冒泡排序
 * @param arr
 * @param len
 * @param sort_type
 */
void BulletSort(ElemType arr[], int len, int sort_type)
{
    int temp;
    for (int i = 0; i < len; ++i)
    {
        for (int j = 0; j < len - 1 - i; ++j)
        {
            if (sort_type)
            {
                if (arr[j] > arr[j + 1])
                {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            } else
            {
                if (arr[j] < arr[j + 1])
                {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

/**
 * 插入排序:适合少量数据
 * @param arr
 * @param len
 * @param sort_type
 */
void InsertSort(ElemType arr[], int len, int sort_type)
{
    int temp, j, i;
    for (i = 1; i < len; ++i)
    {
        temp = arr[i];
        j = i - 1;
        if (sort_type)
        {
            while (j >= 0 && temp < arr[j])
            {
                arr[j + 1] = arr[j];
                --j;
            }
        } else
        {
            while (j >= 0 && temp > arr[j])
            {
                arr[j + 1] = arr[j];
                --j;
            }
        }
        arr[j + 1] = temp;
    }

}

/**
 * 快速排序
 * @param arr
 * @param len
 * @param sort_type
 */
void QuickSort(ElemType *arr, int left, int right, int sort_type)
{
    int i = left, j = right;
    int temp;
    if (left >= right)return;
    while (i <= j)
    {
        while (i <= j && arr[left] >= arr[i]) ++i; //找出左边比arr[left]大的元素
        while (i <= j && arr[left] <= arr[j]) --j; //找出右边比arr[left]小的元素
        if (i < j)
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; //交换完之后移向下一个位置
            --j;
        }
    }
    //经过循环后在j位置就是标杆的位置，这个位置左边都不大于该值，该位置右边都不小于该值
    temp = arr[left];
    arr[left] = arr[j];
    arr[j] = temp;
    QuickSort(arr, left, j - 1, 1);
    QuickSort(arr, j + 1, right, 1);
}

/**
 * 希尔排序
 * 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
 * @param arr
 * @param len
 */
void ShellSort(ElemType *arr, int len)
{
    int d = len / 2;
    int i, j;
    int temp;
    //由希尔排序要进行的次数来决定（每一次都有相应的分组情况，即有不同的增值）
    while (d > 0)
    {
        // 对该次希尔排序（分组情况）进行插入排序（由要进行插入排序的元素个数来决定）
        for (i = d; i < len; ++i)
        {
            //本来一个插入排序从1开始，这里有d组插入排序，所以从d开始
            //这个是d组一起进行插入排序，即等到每一组都插入第i个元素后，才会进行插入第i+1个元素
            temp = arr[i];
            //将每次的元素插入(由有序元素的个数来决定)
            for (j = i - d; j >= 0 && temp < arr[j]; j = j - d)
            {
                arr[j + d] = arr[j];
            }
            arr[j + d] = temp;
        }
        d = d / 2; //从新分组
    }
}


/**
 * 基数排序
 * 基数排序，第一步根据数字的个位分配到每个桶里，在桶内部排序，然后将数字再输出（串起来）；然后根据十位分桶，继续排序，再串起来。直至所有位被比较完，所有数字已经有序。
 * @param arr
 * @param len
 */
void RadixSort(ElemType *arr, int len)
{
    int temp[10][20];
    int index;
    for (int n = 1; n <= 100; n *= 10)
    {
        for (int x = 0; x < 10; ++x)
        {
            for (int y = 0; y < 20; ++y)
            {
                temp[x][y] = -1;
            }
        }

        for (int i = 0; i < len; ++i)
        {
            index = (arr[i] / n) % 10;
            temp[index][i] = arr[i];
        }
        int count = 0;
        for (int i = 0; i < 10; ++i)
        {
            for (int j = 0; j < 20; ++j)
            {
                if (temp[i][j] != -1)
                    arr[count++] = temp[i][j];
            }
        }
    }
}

/**
 * 归并排序
 * 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
 * @param arr
 * @param left
 * @param mid
 * @param right
 */
void MergeInArr(ElemType *arr, int left, int right, ElemType *newAttr)
{
    //注意此时左右空间都是各自有序
    //int length=right-left+1; //辅助数组长度
    if (left >= right)
    {
        return;
    }
    int mid = (left + right) >> 1;
    MergeInArr(arr, left, mid, newAttr);
    MergeInArr(arr, mid + 1, right, newAttr);

    int start1 = left;
    int end1 = mid;
    int start2 = mid + 1;
    int end2 = right;

    int index = left;

    //合并
    while (start1 <= end1 && start2 <= end2)
    {
        if (arr[start1] <= arr[start2])
        {
            newAttr[index] = arr[start1];
            ++index;
            ++start1;
        } else
        {
            newAttr[index] = arr[start2];
            ++index;
            ++start2;
        }
    }
    while (start1 <= end1)
    {
        newAttr[index] = arr[start1];
        ++index;
        ++start1;
    }

    while (start2 <= end2)
    {
        newAttr[index] = arr[start2];
        ++index;
        ++start2;
    }

    while (left <= right)
    {
        arr[left] = newAttr[left];
        ++left;
    }

}

/**
 * 归并排序
 * @param arr
 * @param len
 */
void MergeSort(ElemType arr[], int len)
{
    int *newArr = (int *) (malloc(sizeof(int) * len));
    MergeInArr(arr, 0, len - 1, newArr);
    free(newArr);
}

void swap(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void HashInsert(int *arr)
{
    int len = sizeof(arr) / arr[0];
    for (int i = 0; i < len; i++)
    {
        int currentIndex = i;
        //父结点
        int fatherIndex = (currentIndex - 1) / 2;
        while (arr[currentIndex] > arr[fatherIndex])
        {
            swap(arr, currentIndex, fatherIndex);
            currentIndex = fatherIndex;
            fatherIndex = (currentIndex - 1) / 2;
        }
    }
}

void Hashify(int *arr, int index, int size)
{
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    while (left < size)
    {
        int largestIndex;
        if (arr[left] < arr[right] && right < size)
        {
            largestIndex = right;
        } else
        {
            largestIndex = left;
        }
        if (arr[index] > arr[largestIndex])
        {
            largestIndex = index;
        }
        if (index == largestIndex)
        {
            break;
        }
        swap(arr, largestIndex, index);
        index = largestIndex;
        left = 2 * index + 1;
        right = 2 * index + 2;
    }
}

/**
 * hashsort
 * @param arr
 */
void HashSort(int *arr)
{
    HashInsert(arr);
    int size = sizeof(arr) / arr[0];
    while (size > 1)
    {
        swap(arr, 0, size - 1);
        size--;
        Hashify(arr, 0, size);
    }
}